\chapter{Introduction}

\section{Background}

Simulation of ocean waves can be categorized into two major groups. First one is based on the physical models whereas the other generates the ocean waves based on either geometrical shapes or oceanography spectrums. Even though the later method group requires less computational effort, the waves modeled are less realistic in nature.\par

Currently MARIN (Maritime Research Institute Netherlands) provides ship maneuvering simulators. Computation of the wave field is based on the wave spectra (Fourier theory). Being deterministic in time and space; they are easy to implement on distributed simulation systems. Also the ship movements are realistic. However, this model is not interactive, that is impact of the ship movement on the wave field is not taken into account. Also, from a visualization point of view, the model is limited.\par

In theory, for fluid simulation, the non-linear Navier Stokes equations along with the equation of continuity are solved. Boussinesq's approximation for water waves is applied for weakly non-linear and fairly long waves. The essential idea in the Boussinesq approximation is the elimination of the vertical coordinate from the flow structure, while still retaining some of the influence of the vertical structure of the flow. This is possible because wave propagates in the horizontal direction, whereas it has a different non-wave like behavior in the vertical direction. In Boussinesq-like models, an approximate vertical structure of the flow is used to eliminate the vertical space.\par


\textbf{Frequency dispersion:} Water waves exhibit frequency dispersion, i.e. water waves of different wave lengths travel with different phase speeds.
Classical Boussinesq models are limited to long waves - having wavelengths much longer than the water depth.\par


The variational Bousinnesq model (developed by Gert Klopman \cite{Klopman}) can deal with deep waters with varying depth, as the vertical structure is treated as a function of depth, surface elevation and other parameters. The big advantage over the deterministic model is that it can incorporate the influence of the ship movement, thus making it an interactive wave model. Owing to the variation in the vertical structure and its interactive nature, it is much more computational intensive, and much work has been done in order to improve the running time of the solver. Two previous master thesis by Van't Wout \cite{Wout} and De Jong \cite{Jong} have focused on creating a fast linear solver and increasing the efficiency by GPU programming.

\section{Earlier Work}

\subsection{Elwin van't Wout: Fast solver and model explanation}

Elwin's work \cite{Wout} comprised of improving the linear solver that is used in a real-time ship simulator. The underlying wave model is the variational Boussinesq model as suggested by Gert Klopman \cite{Klopman}. Elwin starts with derivation of the Variational Boussinesq Model (VBM). Starting point of the derivation of the model equations are the Euler equations which are valid for motions of ideal fluids and are a special case of the Navier-Stokes equations  (inviscid incompressible flow). In order to reduce the problem from 3 dimensions to 2 dimensions, vertical shape functions are employed. The resulting model is linearized to reduce complexity. The linearized model is described in detail in \Cref{Chapter2}.

Equations are then discretized (spatially) using a finite volume method with structured Cartesian grids. Time integration is performed using a leap-frog scheme. One of the equations results in a system of linear equations. Elwin provides a detailed description of various numerical methods available for solving linear system of equations. Based on the properties of the matrix involved, he selects the Conjugate Gradient method as solver. This iterative method is then combined with various preconditioners, namely diagoal scaling, modified incomplete Cholesky and repeated red black ordering. Elwin modified the original implementation of the repeated red black-preconditioner to a repeated red black preconditioner for a predefined number of levels, combined with a complete Cholesky decomposition on the maximum level. Elwin concludes that the repeated red black preconditioner is the method with the lowest amount of computation time, in most of the cases.


\subsection{Martin De Jong: Developing a CUDA solver for large sparse matrices for MARIN}
The C++ RRB solver developed by Elwin was able to solve the system of linear equations within 50 ms for domains no bigger than 100,000 to 200,000 nodes. The focus of Martijn's thesis was to increase the performance of above solver by utilizing GPU architecture. By carefully selecting the storage data structures, optimal CUDA programming parameters, Martijn was able to achieve a speedup of 30x as compared to the serial code. Martijn reports that the new solver can solve systems that have more than 1.5 million nodes within 50ms with ease.

\section{Current Work and Organization Of the Report}
Our main target is to explore different approaches to increase the performance of the current time dependent solver, and allow solution to large problems in a similar runtime. Literature review on the project will focus upon exploring implicit time integration approaches, and non-uniform grid formulation.
The organization of the report is given below:

\begin{enumerate}
\item Chapter 2 describes the governing equations and discretization.
\item Chapter 3 discusses previous implementation by Martijn, the RRB solver and its key features.
\item Chapter 4 discusses the implicit time integration techniques.
\item Chapter 5 discusses linear solvers for non-symmetric matrices.
\item Chapter 6 discusses the required research.
\end{enumerate}


